<?php 
/** 
 * 变态跳台阶
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 * 当有n个台阶
 * 当最后一次跳 1 台阶 前面有 f(n - 1) 种
 * 	            2             f(n - 2)
 * 	            3             f(n - 3)
 * 	            .                ...
 * 	            n -1          f(n - (n - 1))
 * 	            n             f(n - n);
 * 所以 f(n) = f(n - 1) + f(n - 2) + f(n - 3) + ... + f(n - (n - 1)) + f(n - n);
 * 同理 f(n - 1) = f(n -2) + f(n - 3) + ... + f((n - 1) - ((n - 1) - 1)) +f ((n-1) - (n - 1)) 
 * 推出 f(n) = 2 * f(n - 1);
 */

function jumpFloorII($number)
{
    if ($number == 0) {
    	return 0;
    }
    if ($number == 1) {
    	return 1;
    }
    return 2 * jumpFloorII($number - 1);
}

echo jumpFloorII(3);